When an object in which various surfaces are complicatedly combined, like a living thing (e.g., a human being or an animal) or an artifact (e.g., a car or an air plane), is processed by three-dimensional computer graphics, modeling of its shape is generally performed by three-dimensional measurement of the actual thing or a model. In recent years, since CAD (Computer Aided Design) capable of handling free surfaces has been developed, when an artifact, such as a car or an air plane, is designed using CAD, modeling of the artifact can use design data of CAD. In any case, such shape data is expressed by the following sequences: a sequence of three-dimensional coordinate points with indexes of points on the surface of the object, a sequence of three-dimensional vector points with indexes of normal vectors on the surface of the object, a sequence of three-dimensional (or two-dimensional) coordinate points with indexes of three-dimensional (or two-dimensional) texture coordinates used when a texture is mapped on the surface of the object, and a sequence of these indexes. The size of these sequences of points and vectors depends on the shape of the object. For example, a rough shape consists of several hundreds of sequences, and a minutely modeled shape consists of thousands to tens of thousands of sequences. Therefore, techniques for compressing shape data are required.
An example of a data compression technique is to reduce the amount of shape data by approximating the shape of an object using polygonal patches or parametric surfaces. This method is described in detail in Japanese Published Patent Application No. Hei. 4-202151, "Three-dimensional Shape Input Apparatus". In this method, to reduce the amount of shape data, it is necessary to reduce, i.e., thin out, vertexes of the polygonal patches or control points of the parametric surfaces. However, since the shape data is expressed by sequences of points, it is impossible to thin out control points of parametric surfaces. Therefore, the only way left is to thin out vertexes of polygons, that is, to thin out points on the surface. However, since a method for deciding which points are to be deleted from enormous number of sequences of points is not given, selection of points to be deleted cannot be performed. If it is performed in utter disregard of the shape, the shape is deformed and the shape data cannot be used at all. Further, normal vectors and texture coordinates corresponding to the points deleted must be deleted, and index sequences must be changed. Since the shape data is enormous as mentioned above, these operations are extremely difficult.
Meanwhile, another example of a data compression method is proposed in Japanese Published Patent Application No. Hei. 5-333859, "Shape Data Compression Method and Shape Data Decompression Method". In this method, it is premised that an object shape which is hierachized in parts is employed. When an object shape which is not hierachized is employed, it must be divided into parts and then hierachized. Data compression is performed for each part, and the compression method employs a transformation formula between a vertex coordinate of the shape of the part and a quantized coordinate.
In this method, although it is premised that a hierachized object shape should be used or an object shape should be hierachized, since shape data are not hierachized in most cases, hierachization must be carried out. In this prior art, described that "hierarchical division of an object shape into parts is realized by dividing a distribution area of vertexes while considering connections between these vertexes". To achieve this operation, the operator must know connections between points in point sequences, but it is impossible to know such connections in enormous number of point sequence data. Therefore, the only substantial method is to divide the object shape according to distribution of point sequences, but this division cannot secure hierachization adapted to the actual state. Even though shape data is hierachically divided into parts, the respective parts, for example, in case of a human being, upper and lower arms, trunk, and other parts, will have complicated shapes in which symmetry and the like are not secured at all.
As mentioned above, data compression is performed for each part, and the compression method employs a transformation formula between a vertex coordinate of the shape of the part and a quantized coordinate. To be specific, it is performed using a transformation formula between a partial point sequence that defines the shape of the part and a quantized coordinate sequence. According to the second prior art mentioned above, to calculate the transformation formula, a principal axis transformation must be found first. However, the principal axis transformation according to the second prior art is only applicable to an object of a simple shape, such as a cube, and a calculation method of a principal axis transformation for a complicated shape as mentioned above has not been discovered yet. Consequently, it is impossible to compress shape data in which various surfaces are combined complicatedly.